Atcoder abc173 题解

注意到每个人来的顺序不是固定的，而且第一个人是拿不到舒适值的，可以想到第一个人一定是$A_i$最大的人，因为假如第二个人较小则获得的收益降低，若相同则不影响，结果不会变差。

其次可以拓展出整个过程肯定也是先选大的进去比较好，所以整个序列的编排顺序应该是从大到小依次插入的。每次应该选择整个序列中次大的值。由于可以插入到任意位置之间，这导致一个人实际上可以用两次，因为这个人会有两个相邻的人在，就可以放在两边算两次了(可以画图辅助理解一下)。

因此我们维护一个优先队列即可：第一权值是本身的值$A_i$，第二权值是当前使用过的次数，假如次数是$0$的话，那么还可以入队一起，否则就直接不管，踢出队列不加回来。每次对新的$A_i$查询次大值即可。

到这里实际上还不能完整做完本题。首先对于第二个人来说它来检测的时候肯定就没有次大值，这个时候可能就要特判掉他（之前就加入）这个时候就有一个坑点了，最大值的那个人次数不能是$0$而应该是$1$，因为这个最大值是被第二个人用过的，如果不加会$WA$掉两个点。最后记得开LL就行。

首先肯定是排个序，完了之后肯定要从两边去选（存在负数的问题）。可以发现，由于负数是两两选择的，我们也同样可以在正数的选择策略上选择同样的方式。即排序之后从两边两两选择。
假如说$k$是个奇数，首先削掉$A_n$，最大的肯定要选进去。假如说最大的都是负数，则后面的肯定也要选一个负数乘积出来，特殊标记一下。

之后两两选数，从起点和末尾分别开始，选两边较大的一对数加入答案，由于说有上面的特殊标记的问题，所以两边算出来的乘积需要再乘上特殊标记，因为在有标记的时候是要找出负数最小的乘积，反之则是最大的。注意一下就行。正确性比较显然，削掉奇数的情况之后两两选择也肯定能选完。

不过本题还涉及到负数取余的问题，注意在最后把$res$取余调回正数就可以了。

这个式子想拆看着也很难拆，又是两个求和，考虑算单个贡献。
第一个比较容易想到的结论就是：联通块的数量=点数 - 边数。由于范围特别大，只能说遍历一下每个点，于是顺理成章的我们来考虑单个点$x$对整个答案的贡献是怎样的。
首先对于点数，假如说$x$产生了贡献，那么他对某个产生了贡献的区间满足$L \leq x \leq R$，进而可以算出对于单个点来说他一共会对点数产生$x * (n - x + 1)$的贡献。
其次对于边数，假如说当前的边连接的两个分别是$u$和$v$，那么这个边产生贡献，当且仅当$u$和$v$都产生了贡献时，也就是说他俩都被算进图里的时候才会有贡献。那么下界肯定是较小者，上界是较大者，假设$u < v$(否则可以交换)，那么产生的边的贡献就是$u *(n - v +1)$，分别计算点数和边数贡献，最终就可以求的答案了。